//
// Created by wenyaxi on 24-10-29.
//
#include <common.h>

class Solution {
public:
    int m, n;

    int numIslands(vector<vector<char> > &grid) {
        m = grid.size(), n = grid[0].size();
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    ans++;
                    dfs(grid, i, j);
                }
            }
        }
        return ans;
    }

    void dfs(vector<vector<char> > &grid, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
};

int main(int argc, char *argv[]) {
    Solution s;
    /*[
     *  ["1","1","1","1","0"],
     *  ["1","1","0","1","0"],
     *  ["1","1","0","0","0"],
     *  ["0","0","0","0","0"]
     *]
     *
     */
}
